#define FALSE 0
#define TRUE 1
#define SIZE 100

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tree_node{
	char data;
	struct tree_node *left;
	struct tree_node *right;
}TreeNode;

typedef struct tree{
	TreeNode *root;
}Tree;

typedef int BOOL;

BOOL isOpr(char ch)
{
	switch(ch)
	{
	case '+':
		return TRUE;
	case '-':
		return TRUE;
	case '*':
		return TRUE;
	case '/':
		return TRUE;
	default:
		return FALSE;
	}
}

int needTrim(char *str, unsigned int len)
{
	int stack = 0;
	if(!(str[0]=='(') || !(str[len-1]==')')) return 0;
	for(int i=0;i<len - 1;i++)
	{
		if(str[i] == '(') stack++;
		else if(str[i] == ')') stack--;
		if(stack == 0) return 0;
	}
	if(stack) return 1;
	return 0;


}

TreeNode *ExpNode(char *str, unsigned int  len)
{
	TreeNode *ret;
	ret = malloc(sizeof(TreeNode));
	if(len == 0) return NULL;
	if(len == 1)
	{
		ret->left = NULL;
		ret->right = NULL;
		ret->data = str[0];
		return ret;
	}
	if(needTrim(str, len)) return ExpNode(str+1, len-2);
	for(int i=1;i<len-1;i++)
		if(isOpr(str[i]) &&( (str[i+1] == '(')&&(str[i-1] == ')')))
		{
			ret->data = str[i];
			ret->left = ExpNode(str, i);
			ret->right = ExpNode(str + i + 1, len - i - 1);
			return ret;
		}
	for(int i=1;i<len-1;i++)
		if(isOpr(str[i]) &&( (str[i+1] == '(')||(str[i-1] == ')')))
		{
			ret->data = str[i];
			ret->left = ExpNode(str, i);
			ret->right = ExpNode(str + i + 1, len - i - 1);
			return ret;
		}
	for(int i=0;i<len;i++)
		if(isOpr(str[i]))
		{
			ret->data = str[i];
			ret->left = ExpNode(str, i);
			ret->right = ExpNode(str + i + 1, len - i - 1);
			return ret;
		}
	return NULL;

}

BOOL sanityCheck(char *str)
{
	int stack = 0;
	for(int i=0;i<strlen(str);i++)
	{
		if(str[i]=='(') stack++;
		else if(str[i]==')') stack--;
	}
	return !stack;
}

BOOL buildExpressionTree(char *str, Tree *tr)
{
	if(!sanityCheck(str)) return FALSE;
	tr->root = ExpNode(str, strlen(str));
	return TRUE;
}

double calcExp(TreeNode *n)
{
	switch(n->data)
	{
	case '+':
		return calcExp(n->left) + calcExp(n->right);
	case '-':
		return calcExp(n->left) - calcExp(n->right);
	case '*':
		return calcExp(n->left) * calcExp(n->right);
	case '/':
		return calcExp(n->left) / calcExp(n->right);
	default:
		return n->data - '0';
	}

}

double calcExpression(Tree tr)
{
	return calcExp(tr.root);

}

void printTree(TreeNode *n)
{
	if(!n) return;
	printf("%c\t",n->data);
	printTree(n->left);
	printTree(n->right);
}

void freeTree(Tree tr)
{

}

int main()
{
	char str[SIZE];
	Tree tr;
	double res;
	BOOL expressionOK;
	printf("Please enter the expression: ");
	gets(str);

	expressionOK = buildExpressionTree(str, &tr);
	//printTree(tr.root);
	printf("\n");

	if(expressionOK == TRUE)
	{
			res = calcExpression(tr);
			printf("%s = %.2f", str, res);
	}
	else
		printf("The input expression is not valid\n");
	freeTree(tr);
}
